COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	decida[w85,jmc]		Decidable problems as an AI tool
C00004 ENDMK
C⊗;
decida[w85,jmc]		Decidable problems as an AI tool

1. The object of this note is to formulate the decidability
of planning problems.  My conjecture is that all the
planning problems that have been considered belong to
decidable domains that have such easy decision procedures
that they can serve as problem solvers.  However, there
are some unstated assumptions in the planning formalisms
and decidability may depend on stating them.

2. In the situation calculus with the usual axioms of the
blocks world it is decidable whether one block is on another
after a given sequence of actions has been performed.  However,
it is not decidable whether there exists an action that
achieves a goal, because we have no axioms that limit the
set of actions, i.e. there may be an unmentioned action
that immediately brings about the desired state of affairs.
But it is decidable in the easy cases as to whether there is
an action that can be proved to achieve the goal, because there
we can only consider the known actions.  If we circumscribe
the actions to the known ones (how to formalize this?), we
can then decide whether the goal is achievable.

	It is worthwhile to work this out in detail.  How can
a formulate it to get someone else to do it.